This invention relates to arbitration apparatus. The invention is particularly, although not exclusively, concerned with an arbitration apparatus for distributing message traffic over a data transmission network.
By "arbitration" is meant a process of deciding which of a number of currently active jobs is to be scheduled next, in such a way as to achieve a proper balance between the different jobs. For example, in a data transmission network, a job may consist of sending a datagram or message from a particular source to a particular destination, and in this case arbitration may be required to distribute message traffic evenly between the different possible destinations, so as to ensure that particular parts of the network do not become overloaded.
One way of performing arbitration is to maintain a list of possible jobs, and to scan this list cyclically, looking for currently active jobs. However, a problem with this is that, if the overall number of jobs is relatively large, and the number of active jobs is small, the arbitration mechanism may spend an excessive amount of time scanning through non-active entries in the list. In the case of a data transmission network, for example, this may lead to an unacceptable reduction in transmission rate.
Alternatively, arbitration may be performed by a decision logic circuit, which examines all the entries in the job list in parallel, so as to select the next active job. However, such logic circuits are practical only where the number of entries in the job list is relatively small, and do not easily scale up to larger lists. For example, if the job list contains 64 entries (corresponding for example to 64 possible destinations in a network), the fan-in to the decision logic becomes unmanageable.
The object of the present invention is to provide an arbitration circuit capable of rapid operation, and capable of efficiently handling relatively large, variable sized job lists.